package main

import (
	"fmt"
)

/**
执行用时：124 ms, 在所有 Go 提交中击败了40.90%的用户
内存消耗：24.7 MB, 在所有 Go 提交中击败了52.11%的用户
 */
func firstMissingPositive(nums []int) int {

	n := len(nums)

	for i := 0; i < n; i++ {
		t := &nums[i]  // 要保证nums[i]变化时t也变化
		for *t > 0 && *t <= n && nums[*t - 1] != *t {
			swap(&nums, i, *t - 1)
		}
	}

	for i := 0; i < n; i++ {
		if nums[i] != i + 1 {
			return i + 1
		}
	}
	return n + 1
}

// 交换nums[i]和nums[j]
func swap(nums *[]int, i int, j int) {
	(*nums)[i], (*nums)[j] = (*nums)[j], (*nums)[i]
}

func main() {

	nums := []int{3, 4, -1, 1}
	fmt.Println(firstMissingPositive(nums))
}
